<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        // 逻辑
        // 冒泡
        // 1 时间复杂度O(n ^ 2) 空间复杂度O(1)
        // 2 逻辑
        // 每个元素和后一个元素比较 当 前一个 大于 后一个 进行交换【需要交换函数】这个元素像泡泡一样 飘到数组的一侧
        // 是稳定排序 -> 不会打乱相同的元素相对位置
        // 是原地排序 -> 没有使用额外的存储空间
        // 每个元素都需要比较一波 => 外层循环是走len - 1次
        // 每个元素比较时，比的次数是 len - 1 - i次 => 内层循环是 len - 1 - i

        // 1. 交换 
        function swap(arr, i, j) {
            let temp = arr[i]
            arr[i] = arr[j]
            arr[j] = temp
        }
        // 2 排序
        function BubbleSort(nums) {
            // debugger
            let len = nums.length
            // 外面for循环 表示走几趟，走 len-1趟
            for (let i = 0; i < len - 1; i++) {
                // debugger
                // 里面的for循环 表示 每一趟走多少次，长度 - i - 1 而i表示当前是第几趟
                for (let j = 0; j < len - i - 1; j++) {
                    // debugger
                    if (nums[j] > nums[j + 1]) {
                        swap(nums, j, j + 1)
                    }
                }
            }
            return nums
        }
        // console.log(BubbleSort([5, 2, 1, 6, 3, 7, 8, 9]));
        let arr = []
        for (let i = 2; i < 10; i++) {
            arr.push(i)
        }
        console.time('排序')
        console.log(BubbleSort([...arr, 1]));
        console.timeEnd('排序')
    </script>
</body>

</html>